서포트 벡터 머신

퍼셉트론은 가장 단순하고 빠른 판별 함수 기반 분류 모형이지만 판별 경계선(decision hyperplane)이 유니크하게 존재하지 않는다는 특징이 있다.

서포트 벡터 머신(SVM: support vector machine)은 퍼셉트론 기반의 모형에 가장 안정적인 판별 경계선을 찾기 위한 제한 조건을 추가한 모형이라고 볼 수 있다.

서포트 벡터 머신의 장점과 단점은 다음과 같다.

  • 장점:

    • 독립 변수의 차원이 큰 경우 효율적
    • 메모리 사용량 적음
    • 다양한 커널 사용 가능
  • 단점:

    • 데이터 수에 비해 차원이 너무 크면 성능 저하

마진

판별 함수 $f(z) = f(w^Tx-w_0)$ 를 가지는 판별 함수 기반 모형의 판별 경계선은 다음과 같이 주어진다.

$$ w^T x - w_0 = 0 $$

이 수식은 경계선에서 0이 된다는 조건만 지키면 되기 때문에 가장 가까운 클래스 +1의 표본 데이터 $x^{+}$과 가장 가까운 클래스 -1의 표본 데이터 $x^{-}의 값이 각각 1과 -1이 되도록 스케일링(scaling)할 수 있다.

$$ w^T x^{+} - w_0 = +1 $$$$ w^T x^{-} - w_0 = -1 $$

이 판별 경계선과 표본 데이터 $x^{+}$, $x^{-}$ 사이의 거리는 다음과 같이 주어진다.

$$ \dfrac{w^T x^{+} - w_0}{\| w \|} $$$$ -\dfrac{w^T x^{-} - w_0}{\| w \|} $$

[[school_notebook:dd1680bfbaab414a8d54dc978c6e883a]]

이 거리의 합을 마진(margin)이라고 하며 마진값이 클 수록 더 경계선이 안정적이라고 볼 수 있다. 그런데 위에서 정한 스케일링에 의해 마진은 다음과 같이 정리된다.

$$ \dfrac{w^T x^{+} - w_0}{\| w \|} -\dfrac{w^T x^{-} - w_0}{\| w \|} = \dfrac{2}{\| w \|}$$

마진 값이 최대가 되는 경우는 $\| w \|$ 즉, $\| w \|^2$가 최소가 되는 경우와 같다.

즉, 서포트 벡터 머신은 값을 최소화 하면서 모든 표본 데이터에 대해 다음 조건을 만족해야 한다.

$$ y \cdot \hat{y} = y \cdot( w^Tx - w_o)\geq 1 $$$$ y \cdot ( w^Tx - w_o) - 1 \geq 0$$

Karush–Kuhn–Tucker 조건을 사용하면 최소화 목적 함수를 다음과 같이 고치면 된다.

$$ L = \dfrac{1}{2} ||w||^2 - \sum_{n=1}^N a_n (y_n \cdot ( w^Tx_n - w_o) - 1 ) $$

Dual Form

위 함수를 $w$, $w_0$ 로 미분하여 기울기가 0이되는 조건을 구하면 다음과 같다.

$$ w = \sum_{n=1}^N a_n y_n x_n $$$$ 0 = \sum_{n=1}^N a_n y_n $$

이 조건을 대입하여 $w$, $w_0$을 없애면 다음과 같은 문제가 된다.

$$ L = \sum_{n=1}^N a_n - \dfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^N a_n a_m y_n y_m x_n^T x_m $$

이 때 $a$는 다음 조건을 만족한다. $$ \sum_{n=1}^N a_n y_n = 0, \;\;\; a_n \geq 0 $$

이 문제는 $w$를 구하는 문제가 아니라 $a$를 구하는 문제로 바뀌었으므로 dual form 이라고도 한다.

dual form 문제는 수치적으로 Box 제한 조건이 있는 이차 프로그래밍 문제(quadratic programming)가 되므로 적은 연산량으로 풀 수 있다.

서포트

dual form 문제를 풀어 함수 $L$ 를 최소화하는 $a$를 구하면 예측 모형을 다음과 같이 쓸 수 있다.

$$ y = w^T x - w_0 = \sum_{n=1}^N a_n y_n x_n^T x - w_0 $$

이차 프로그래밍(최적화)로 구한 $a_n = 0$ 이면 해당 데이터는 예측 모형, 즉 $w$ 계산에 아무런 기여를 하지 않는다는 것을 알 수 있다.

만약 $n$번째 데이터에 대해 $a_n > 0$ 이면 조건 만족을 위해 $y_n(w^Tx_n - w_o) = 1$이 된다. 즉 판별함수 값 $w^Tx_n - w_o = \pm 1$ 이다.

이러한 데이터를 서포트(support)라고 한다.


In [1]:
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=50, centers=2, random_state=4, cluster_std=0.60)

xmin = X[:,0].min()
xmax = X[:,0].max()
ymin = X[:,1].min()
ymax = X[:,1].max()
xx = np.linspace(xmin, xmax, 10)
yy = np.linspace(ymin, ymax, 10)
X1, X2 = np.meshgrid(xx, yy)

def plot_svm(model):
    Z = np.empty(X1.shape)
    for (i, j), val in np.ndenumerate(X1):
        x1 = val
        x2 = X2[i, j]
        p = model.decision_function([[x1, x2]])
        Z[i, j] = p[0]
    levels = [-1.0, 0.0, 1.0]
    linestyles = ['dashed', 'solid', 'dashed']
    plt.scatter(X[:, 0], X[:, 1], c=y, s=100, cmap=plt.cm.Paired)
    plt.contour(X1, X2, Z, levels, colors='k', linestyles=linestyles)
    plt.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=150, linewidth=3, facecolors='none')
    plt.show()

from sklearn.svm import SVC

model = SVC(kernel='linear').fit(X, y)
plot_svm(model)



In [2]:
x_new = [10, 2]
model.decision_function([x_new])


Out[2]:
array([-0.70648511])

In [3]:
model.coef_.dot(x_new) + model.intercept_


Out[3]:
array([-0.70648511])

In [4]:
model.support_vectors_


Out[4]:
array([[ 8.97646441,  1.87283258],
       [ 9.11476202,  3.37056244]])

In [5]:
model.support_


Out[5]:
array([42,  1], dtype=int32)

In [6]:
y[model.support_]


Out[6]:
array([0, 1])

In [7]:
# dual_coef_ = y_i \alpha_i
model.dual_coef_[0][0] * model.support_vectors_[0].dot(x_new) + \
model.dual_coef_[0][1] * model.support_vectors_[1].dot(x_new) + \
model.intercept_


Out[7]:
array([-0.70648511])

In [8]:
y[model.support_][1]


Out[8]:
1

In [9]:
model.n_support_


Out[9]:
array([1, 1], dtype=int32)

슬랙 변수

만약 데이터가 직선인 판별 경계선으로 나누어지지 않는 즉, 선형 분리(linear separable)가 불가능 한 경우에는 다음과 같이 슬랙 변수(slack variable)를 사용하여 개별적인 오차를 허용할 수 있다.

원래 판별 함수의 값은,

클래스 $+1$ 영역의 샘플 $x_{+}$에 대해

$$ w^Tx_{+} - w_0 \geq 1 $$

클래스 $-1$ 영역의 샘플 $x_{-}$에 대해

$$ w^Tx_{-} - w_0 \leq -1 $$

이어야 한다.

양수인 슬랙 변수 $\xi \geq 0 $를 사용하면 이 조건을 다음과 같이 완화할 수 있다.

$$ w^Tx_{+} - w_0 \geq +1-\xi_i $$$$ w^Tx_{-} - w_0 \leq -1+\xi_i $$$$ \xi \geq 0 $$

대신 슬랙 변수의 크기를 제한해야 하므로 위의 부등식 조건을 모두 고려한 최적화 목적 함수는 다음과 같아진다.

$$ L = \dfrac{1}{2} ||w||^2 - \sum_{n=1}^N a_n (y_n \cdot ( w^Tx_n - w_o) - 1 + \xi_n ) - \sum_{n=1}^N \mu_n \xi_n + C \sum_{n=1}^N \xi_n $$


In [10]:
np.random.seed(0)
X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]
Y = [0] * 20 + [1] * 20

fignum = 1
for name, penalty in (('C=1', 1), ('C=0.05', 0.05)):
    clf = SVC(kernel='linear', C=penalty).fit(X, Y)
    w = clf.coef_[0]
    a = -w[0] / w[1]
    xx = np.linspace(-5, 5)
    yy = a * xx - (clf.intercept_[0]) / w[1]
    margin = 1 / np.sqrt(np.sum(clf.coef_ ** 2))
    yy_down = yy + a * margin
    yy_up = yy - a * margin
    
    plt.figure(fignum)
    
    x_min = -5
    x_max = 5
    y_min = -9
    y_max = 9
    XX, YY = np.mgrid[x_min:x_max:200j, y_min:y_max:200j]
    Z = clf.predict(np.c_[XX.ravel(), YY.ravel()])
    Z = Z.reshape(XX.shape)
    plt.contourf(XX, YY, Z, cmap=plt.cm.Accent, alpha=0.6)

    plt.plot(xx, yy, 'k-')
    plt.plot(xx, yy_down, 'k--')
    plt.plot(xx, yy_up, 'k--')
    plt.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1], s=120, linewidth=4, facecolors='none')
    plt.scatter(X[:, 0], X[:, 1], c=Y, s=60, linewidth=1, cmap=plt.cm.Paired)

    plt.xlim(x_min, x_max)
    plt.ylim(y_min, y_max)
    plt.xticks(())
    plt.yticks(())
    plt.title(name)
    plt.axis('tight')
    plt.show()
    
    fignum = fignum + 1;


얼굴 이미지 인식


In [16]:
from sklearn.datasets import fetch_olivetti_faces
faces = fetch_olivetti_faces()

N=2; M=5;
np.random.seed(0)
fig = plt.figure(figsize=(9,5))
plt.subplots_adjust(top=1, bottom=0, hspace=0, wspace=0.05)
klist = np.random.choice(range(len(faces.data)), N * M)
for i in range(N):
    for j in range(M):
        k = klist[i*M+j]
        ax = fig.add_subplot(N, M, i*M+j+1)
        ax.imshow(faces.images[k], cmap=plt.cm.bone);
        ax.grid(False)
        ax.xaxis.set_ticks([])
        ax.yaxis.set_ticks([])
        plt.title(faces.target[k])
plt.tight_layout()
plt.show()



In [17]:
from sklearn.cross_validation import train_test_split
X_train, X_test, y_train, y_test = train_test_split(faces.data, faces.target, test_size=0.25, random_state=0)

In [18]:
from sklearn.svm import SVC
svc_1 = SVC(kernel='linear').fit(X_train, y_train)

In [20]:
fig = plt.figure(figsize=(3,30))
for i, k in enumerate(np.random.choice(len(y_test), 10)):
    ax = fig.add_subplot(10, 1, i + 1)
    ax.imshow(X_test[k:(k+1), :].reshape(64,64), cmap=plt.cm.bone);
    ax.grid(False)
    ax.xaxis.set_ticks([])
    ax.yaxis.set_ticks([])
    plt.title("actual %d => predict %d" % (y_test[k], svc_1.predict(X_test[k:(k+1), :])[0]))
plt.tight_layout()
plt.show()



In [22]:
glasses = [
    ( 10,  19), ( 30,  32), ( 37,  38), ( 50,  59), ( 63,  64),
    ( 69,  69), (120, 121), (124, 129), (130, 139), (160, 161),
    (164, 169), (180, 182), (185, 185), (189, 189), (190, 192),
    (194, 194), (196, 199), (260, 269), (270, 279), (300, 309),
    (330, 339), (358, 359), (360, 369)
]

def create_target(segments):
    y = np.zeros(faces.target.shape[0])
    for (start, end) in segments:
        y[start:end + 1] = 1
    return y

target_glasses = create_target(glasses)
X_train, X_test, y_train, y_test = train_test_split(faces.data, target_glasses, test_size=0.25, random_state=0)

In [23]:
svc_2 = SVC(kernel='linear').fit(X_train, y_train)

In [25]:
fig = plt.figure(figsize=(3,30))
for i, k in enumerate(np.random.choice(len(y_test), 10)):
    ax = fig.add_subplot(10, 1, i + 1)
    ax.imshow(X_test[k:(k+1), :].reshape(64,64), cmap=plt.cm.bone);
    ax.grid(False)
    ax.xaxis.set_ticks([])
    ax.yaxis.set_ticks([])
    plt.title("prediction: %s" %  ("glasses" if (svc_2.predict(X_test[k:(k+1), :])[0]) else "no glasses"))
plt.tight_layout()
plt.show()